/*和为 K 的子数组
class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        int n = nums.length, count = 0;
        // dp
        int[] dp = new int[n];
        hash.put(0,1);
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
            if (hash.containsKey(dp[i] - k)) {
                count += hash.getOrDefault(dp[i]-k,0);
            }
            hash.put(dp[i], hash.getOrDefault(dp[i], 0) + 1);
        }
        return count;

    }

    找到字符串中所有字母异位词
    class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int m = p.length(), n = s.length();
        HashMap<Character, Integer> hash1 = new HashMap<>();
        for (int i = 0; i < m; i++) {
            char ch = p.charAt(i);
            hash1.put(ch, hash1.getOrDefault(ch, 0) + 1);
        }
        HashMap<Character, Integer> hash2 = new HashMap<>();
        int left = 0;
        for (int right = 0; right < n; right++) {
            char ch = s.charAt(right);
            // 进窗口
            hash2.put(ch, hash2.getOrDefault(ch, 0) + 1);
            // 判断
            while (right - left + 1 > m) {
                char ch1 = s.charAt(left);
                int count = hash2.get(ch1) - 1;
                if (count == 0) {
                    hash2.remove(s.charAt(left));
                } else {
                    hash2.put(ch1, count);
                }
                left++;
            }
            // 出窗口 此时为hash2的个数和hash1的个数相同 更新结果
            if (hash2.equals(hash1)) {
                ret.add(left);
            }
        }
        return ret;
    }
}
}*/
